import java.util.*;

/**
 * @author LKQ
 * @date 2022/7/9 9:05
 * @description 动态规划
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8};
        solution.lenLongestFibSubseq(arr);
    }
    public int lenLongestFibSubseq(int[] arr) {
        // 记录每个键的位置
        Map<Integer, Integer> map = new HashMap<>();
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            map.put(arr[i], i);
        }
        // dp[j][i]定义为以 arr[j]和 arr[i]结尾的最长递增子序列结尾两个字段的长度
        int[][] dp = new int[n][n];
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i - 1; j >= 0 && arr[j] * 2 > arr[i] ; j--) {
                int k = map.getOrDefault(arr[i] - arr[j], -1);
                if (k >= 0) {
                    // 说明存在，而且最少长度为3
                    dp[j][i] = Math.max(dp[k][j] + 1, 3);
                }
                cnt = Math.max(cnt, dp[j][i]);
            }
        }
        return cnt;
    }
}
